"""This module contains common functions and classes used when manipulating lists. 
""" 

"""Project Euler Solutions Library

Copyright (c) 2011 by Robert Vella - robert.r.h.vella@gmail.com

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
"""

from euler.core import infinity
from functools import reduce
from itertools import islice
from itertools import groupby

def join(iterable):
    """Returns all the lists in [iterable] joined together."""
    return reduce(lambda list1, list2: list1 + list2, iterable)

def max_by(evaluator, iterable):
    """Returns the element in [iterable] for which the function, [evaluator],
    returns the maximum value.
    """
        
    return max(iterable, key = evaluator)

def true_product(iterable):
    """Returns all the elements of [iterable] multiplied together."""
    
    result = 1
    
    for currentNumber in iterable:
        result *= currentNumber
        
    return result

def first(iterable):
    """Returns the first element generated by [iterable]."""
    
    try:
        return next(iterable)
    except StopIteration:
        return None
    
def last(iterable):
    """Returns the last element generated by [iterable]."""
    
    current_item = 0
    
    try:
        while True:
            current_item = next(iterable)
    except StopIteration:
        return current_item
    
def take(n, iterable):
    """Returns the first [n] elements of [iterable]."""
    
    return islice(iterable, 0, n)

def overlapping_chunks(iterable, chunksize):    
    for i in infinity():
        result = list(islice(iterable, i, i + chunksize))
        if(len(result) < chunksize):
            raise StopIteration
        else:
            yield result
    
    
def ispalindrome(list):    
    """Returns true if [list] is a palindrome."""
    
    #Return true if the first and last element are equal, and the inner
    #elements form a palindrome.     
    return len(list) <= 1 or (list[0] == list[len(list) - 1] \
            and ispalindrome(list[1:len(list) - 1]))    

    
class IndexedValue():
    """A simple constructor which maps a value to an index. This class is 
    mostly used as a return type for the function, index.
    
    Fields:
        index - Another value generated in tandem with [value], as a means to 
            index it.
            
        value - The element generated by the main iterator.
    """
    def __init__(self, index, value):
        self.index = index
        self.value = value
        
def index(iterable, indexer = None):
    """Generates a series of IndexedValue objects containing consecutive 
    elements generated by [iterable] in their value field, and consecutive 
    elements generated by [indexer] in their index field.
    """
    #If no indexer is specified, default to infinity.
    indexer = indexer or infinity()
    
    for item in iterable:
        yield IndexedValue(next(indexer), item)
    
def key_func_pairs(iterable, key, func):
    """Generates the unique set of elements (keys) generated by the function, 
    [key], being applied to each element generated by [iterable]. Each key is
    returned in a tuple containing the key itself, paired with the result
    of the function, [func], being applied to all those elements of [iterable]
    which evaluate to that specific key.
    
    Example:
        iterable=(1, 1, 2, 5, 1, 5);
        key=lambda n : n
        func=lambda group : len(list(group))
        : ((1, 3), (2, 1), (5, 2))
    """
    
    return ((k, func(v)) for k, v in groupby(sorted(iterable, key = key), key))    

def key_count_pairs(iterable, key = lambda n : n):
    """Generates a unique set of elements (keys) generated by the function, 
    [key], being applied to each element generated by [iterable]. Each key is
    returned in a tuple containing the key itself, paired with the number of 
    elements of [iterable] which evaluate to it. If [key] is not specified,
    this function will return all the unique elements and how many times they 
    each occur in [iterable].  
    
    Example:
        iterable=(1, 1, 2, 5, 1, 5): ((1, 3), (2, 1), (5, 2))
        
        iterable=(-1, 1, -1, -1, -5); 
        key = lambda n : n*n
        : ((1, 4), (5, 1))
    """
        
    return key_func_pairs(iterable, key, lambda group : len(list(group)))
    
def key_max_value_pairs(iterable, key):
    """Generates a unique set of elements (keys) generated by the function, 
    [key], being applied to each element generated by [iterable]. Each key is
    returned in a tuple containing the key itself, paired with the largest 
    element of [iterable] which evaluate to it.   
    
    Example:
        iterable=(12,16,18,100,534,333); 
        key = lambda n : int(math.log10(n))
        : ((1, 18), (2, 534))
    """
     
    return key_func_pairs(iterable, key, lambda group : max(group))
